Python数据结构与算法

共计 1250 个字符，预计需要花费 4 分钟才能阅读完成。

算法复杂度分为时间复杂度和空间复杂度。时间复杂度 是指程序要执行的次数，而非执行时间；而 空间复杂度 是指算法执行过程中大概所占用的最大内存空间。计算机资源最重要的是时间和空间 (即寄存器) 资源，因此复杂度分为时间和空间复杂度。

大 O 表示法

大 O 时间复杂度表示法：T(n)=O(f(n))。大 O 时间复杂度实际上并不具体表示代码真正的执行时间，而是表示代码执行时间随数据规模增长的变化趋势，所以，也叫作渐进时间复杂度（asymptotic time complexity），简称时间复杂度。

常见的大 O 数量级函数：

列表常用操作性能

按索引取值和赋值（v=a[i]，a[i]=v），由于列表的随机访问特性，这两个操作执行时间与列表大小无关，均为 O(1)。

列表增长：lst.append(v)，执行时间是 O(1)；lst= lst+[v]，执行时间是 O(n+k)，其中 k 是被加的列表长度。

4 种生成 n 个整数列表的方法：

from timeit import Timer

def t1():
    lst = []
    for i in range(1000):
        lst = lst + [i]

def t2():
    lst = []
    for i in range(1000):
        lst.append(i)

def t3():
    lst = [i for i in range(1000)]

def t4():
    lst = list(range(1000))

time1 = Timer("t1()", "from __main__ import t1")
print("concat:\t\t{} seconds".format(time1.timeit(1000)))

time2 = Timer("t2()", "from __main__ import t2")
print("append:\t\t{} seconds".format(time2.timeit(1000)))

time3 = Timer("t3()", "from __main__ import t3")
print("comprehension:\t{} seconds".format(time3.timeit(1000)))

time4 = Timer("t4()", "from __main__ import t4")
print("list range:\t{} seconds".format(time4.timeit(1000)))

可以看到，4 种方法运行时间差别挺大的，列表连接（+）最慢，中间的是 append 和列表推导式，List range 最快。

字典常用操作性能

与列表不同，字典是根据键值（key）找到数据项，而列表是根据索引（index）。最常用的取值和赋值，其性能均为 O(1)。另一个重要操作 contains(in)是判断字典中是否存在某个键值（key），这个性能也是 O(1)。

更多 Python 数据类型操作复杂度可参考官方文档：https://wiki.python.org/moin/TimeComplexity